package leetcode_core.leetcode_2;

import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists {
    public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //难点在于:如何快速得到k个节点中最小节点,接到结果链表上
    //将链表节点放入一个最小堆,就可以每次获取k个节点中的最小节点
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        ListNode dummy = new ListNode(-1);
        //创建虚拟头节点
        ListNode p = dummy;
        for (ListNode list : lists) {
            //先将最小的头结点加入,开始搜索
            if(list != null){
                pq.add(list);
            }
        }
        while (!pq.isEmpty()){
            //当优先队列非空的时候,继续搜索
            //1.出队
            ListNode poll = pq.poll();
            p.next = poll;
            //2.入队
            if(poll.next != null){
                pq.add(poll.next);
            }
            p=p.next;
        }
        return dummy.next;
    }


}
